/**
 * 
 */
//package practice;
package Simple3;

/**
 * @author Tinatao
 *
 */
public class CoinChange {
		
	public int[] MergeSort(int[] elements){
		int length = elements.length;
		if(elements.length == 1){
			return elements;
		}
		int middle = length/2;
		int left[] = new int[middle];
		int right[] = new int[length - middle];
		for(int i = 0; i != middle; ++i){
			left[i] = elements[i]; 
		}
		for(int i = middle; i != elements.length; ++i)
		{
			right[i - middle] = elements[i];
		}
		left = MergeSort(left);
		right = MergeSort(right);
		int i = 0,j = 0, k = 0;
		for(; j !=left.length && k != right.length; ++i){
			if(left[j] > right[k]){
				elements[i] = left[j];
				++j;
			}
			else{
				elements[i] = right[k];
				++k;
			}
		}
		if(j != left.length){
			for(;j!=left.length;++j,++i){
				elements[i] = left[j];
			}
		} else {
			for(;k!=right.length;++k,++i){
				elements[i] = left[k];
			}
		}
		return elements;
	}
	
	public int greedyChange(int the_coins[],int total){
		int coins[] = MergeSort(the_coins);
		int remain = total;
		int result = 0;
		for(int coin : coins){
			if(remain >= coin){
				result += remain/coin;
				remain = remain%coin;
				if(remain == 0){
					break;
				}
			}
		}
		return result;
	}
	
	public int changeCoin(int the_coins[],int total){
		//int Result = 0;
		int[] opt = new int[total+1];
//		optimal[0] = 0;
		for(int i = 1; i != total+1; ++i){
			opt[i] = total;
		}
		for(int num=1; num<total+1; ++num){
			for(int tempcoin: the_coins){
				if(num>=tempcoin && opt[num]>opt[num-tempcoin]+1){
					opt[num] = opt[num-tempcoin]+1;
				}
			}
		}
		return opt[total];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CoinChange changes = new CoinChange();
		int number = changes.changeCoin(new int[]{1,3,4,5}, 11);
		System.out.println(number);
		number = changes.greedyChange(new int[]{1,3,4,5}, 11);
		System.out.println(number);
		//int test = 3/2;
		
		
	}

}
